The invention relates to encoding and decoding techniques for error correction and detection.
In conventional data storage systems, data being transferred between a processor and a storage device (such as a hard disk) is buffered in memory. Typically, the buffer memory is implemented with semiconductor memory devices such as Dynamic Random Access Memory (DRAM) devices.
Semiconductor memory devices, in particular, DRAMs, are susceptible to errors known as “soft errors”. Soft errors are unexpected or unwanted changes in the value of a bit (or bits) somewhere in the memory. One bit may suddenly, randomly change state, or noise may get stored as if it were valid data. Soft errors are caused by external factors, such as terrestrial cosmic rays.
When soft errors go undetected in a data storage system, erroneous data may be written to disk, or good data read back can be corrupted before it is sent to the processor. In order to provide an acceptable level of reliability for data read from a memory array, therefore, error correcting codes (ECC) such as linear block codes have been employed to correct bit errors in the data stored in the memory. For example, Hamming codes have been used to provide single-bit error correction and double-bit error detection to preserve the data accuracy. As more than two errors cannot be properly detected by the Hamming code, often a Cyclic Redundancy Check (CRC) code is used to supplement the detection capability of the Hamming code. The CRC has no error correction capability, but can detect errors occurring in more than two bits at a time. Together, the Hamming check and CRC can correct single bit errors and detect multi-bit errors reliably.
Conventional linear block codes such as Hamming codes are efficient and easily implemented by using linear feedback shift registers as encoders. During decoding, however, the error locations are indicated by syndromes, which need to be mapped to the actual locations of the errors in the buffer memory. One common approach to this task is to use a large table, which maps the syndromes to the actual memory locations of the errors. The use of such a lookup table incurs additional complexity and cost.